/*
https://leetcode-cn.com/problems/last-stone-weight-ii/solution/zui-hou-yi-kuai-shi-tou-de-zhong-liang-i-95p9/
 */
public class Solution1049 {
    public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for (int stone : stones) {
            sum+=stone;
        }
        int total=sum;
        sum/=2;
        int[] f=new int[sum+1];
        f[0]=1;
        for (int stone : stones) {
            for (int i=sum;i>=0;i--){
                if (i-stone>=0 && f[i]==0 && f[i-stone]==1){
                    f[i]=1;
                }
            }
        }
        for (int i=sum;i>=0;i--){
            if (f[i]==1){
                return total-i*2;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1049().lastStoneWeightII(new int[]{2,7,4,1,8,1}));
    }
}
